package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

import java.util.Arrays;

/**
 * MergeSort average Time Complexity:O(nlogn) comparable
 * Procedure:
 * 1.sort()--->put an array in half
 * 2.merge()--->merge two sorted arrays
 * optimization:
 * 1.reduce the use of merge()
 * 2.when the array is small,using the insertionSort()
 * ****3.use less memory by reducing the copy of original array
 */
public class MergeSort {

    private MergeSort(){

    }

    /**
     * 该方法和merge()方法一起完成归并排序自下到上的实现
     * 分析过程：
     * 1.归并排序：合并两个有序数组，有序
     * 2.自下而上，首先对下面的数组排序，对每一个指定大小的分支数组排序，循环
     * 3.合并已经排序完成的分支数组，弄清过程：
     * 变量：index，size
     * 从“树状图来看”，至少包含两次循环，第一次确定合并的次数，第二次完成对数组的合并
     * for(size=16;size<n;size+=size)
     * 确定基本操作：合并[i,i+size-1]和[i+size,i+size+size-1]
     * for(i=left;i+size<=right;i+=size+size)
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E> > void sortBU(E[] arr) {
        sortBU (arr,0,arr.length-1);
    }
    public static <E extends Comparable<E> > void sortBU(E []arr,int left,int right){

        E []temp=Arrays.copyOf(arr, arr.length);
        int n=arr.length;

        for(int i=left,sz=16;i<right;i=i+sz){
            InsertionSort.sort2 (arr,i,Integer.min (i+sz-1,right));
        }
        
        for(int size=16;size<n;size+=size){
            //[i,i+size-1]  [i+size,i+size+size-1]
            for(int i=left;i+size<=right;i+=size+size){
                if(arr[i+size-1].compareTo(arr[i+size])>0)
                merge2 (arr,i,i+size-1,Integer.min (i+size+size-1,right),temp);
            }
        }
    }
    public static <E extends Comparable<E>> void sort(E []arr){
        sort(arr,0,arr.length-1);
    }

    public static <E extends Comparable<E>> void sort(E []arr,int left,int right){
        if(left>=right)
            return;
        int mid=(left+right)/2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        merge (arr,left,mid,right);
    }
    public static <E extends Comparable<E>> void sort2(E []arr){
        E []temp=Arrays.copyOf(arr, arr.length);
        sort2(arr,0,arr.length-1,temp);
    }

    public static <E extends Comparable<E>> void sort2(E []arr,int left,int right,E[]temp){
        if(left>=right)
            return;
//        if(right-left<=15){
//            InsertionSort.sort2 (arr,left,right);
//            return;
//        }
        int mid=(left+right)/2;
        sort2(arr,left,mid,temp);
        sort2(arr,mid+1,right,temp);
        if(arr[mid].compareTo (arr[mid+1])>0){
            merge2(arr,left,mid,right,temp);
        }
    }
    private static <E extends Comparable<E>> void merge2(E []arr,int left,int mid,int right,E[]temp){

        System.arraycopy (arr,left,temp,left,right-left+1);
        int i=left;
        int j=mid+1;
        for(int k=left;k<=right; k++){
            if(i>mid){
                arr[k]=temp[j];
                j++;
            }else if(j>right){
                arr[k] = temp[i];
                i++;
            }else if(temp[i].compareTo (temp[j])<0){
                arr[k] = temp[i];
                i++;
            }else{
                arr[k] = temp[j];
                j++;
            }
        }
    }

    private static <E extends Comparable<E>> void merge(E []arr,int left,int mid,int right){

        E []temp=Arrays.copyOfRange (arr,left,right+1);
        int i=left;
        int j=mid+1;
        for(int k=left;k<=right; k++){

            if(i>mid){
                arr[k]=temp[j-left];
                j++;
            }else if(j>right){
                arr[k] = temp[i-left];
                i++;
            }else if(temp[i-left].compareTo (temp[j-left])<0){
                arr[k] = temp[i-left];
                i++;
            }else{
                arr[k] = temp[j-left];
                j++;
            }
        }
    }


    public static void main(String[] args) {
        Integer []arr= ArrayGenerator.generateNormalArray (9000000,100000);
        Integer []arr2= ArrayGenerator.generateNormalArray (100,100000);
//        SortingHelper.testSorting (arr,"mergeSort");
        SortingHelper.testSorting (arr2,"mergeSort2");
    }
}
